package DFSTest;

public class Test {
    public  static boolean hasPath (char[][] matrix, String word) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                //从（i，j）这个位置开始查找，然后从word的0的下标开始
                if (dfs(matrix, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    public static boolean dfs(char[][] matrix, String word, int i, int j, int index) {
        if (i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0 ||
                matrix[i][j] != word.charAt(index)){
            return false;
        }
        if(index == word.length()-1) return true;
        char temp=matrix[i][j];
        matrix[i][j]='.';
        boolean ret=dfs(matrix,word,i+1,j,index+1) || dfs(matrix,word,i,j+1,index+1) || dfs(matrix,word,i-1,j,index+1) || dfs(matrix,word,i,j-1,index+1);
        matrix[i][j]=temp;
        return ret;
    }

    public static void main(String[] args) {
        char[][] matrix={{'a','b','c','e'},{'s','f','c','s'},{'a','d','e','e'}};
        String word="abcced";
        boolean ret=hasPath(matrix,word);
    }
}
